#include <bits/stdc++.h>

using namespace std;
class Solution
{
public:
    vector<int> sortArray(vector<int> &nums)
    {
        srand((unsigned int)time(nullptr));
        quicksort(nums,0,nums.size()-1);
        return nums;
    }
    void quicksort(vector<int>&nums, int left,int right)
    {   
        if(left>=right) return;
        int key=nums[left+(rand()%(right-left+1))];
        int index=left;
        int begin=left-1;
        int end=right+1;
        while(index<end)
        {
            if(nums[index]==key) index++;
            else if(nums[index]<key) swap(nums[++begin],nums[index++]);
            else swap(nums[index],nums[--end]);
        }
        quicksort(nums,left,begin);
        quicksort(nums,end,right);
    }
};